package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No90子集II {

    /**
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     *
     * 示例 1：
     * 输入：nums = [1,2,2]
     * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
     * 示例 2：
     * 输入：nums = [0]
     * 输出：[[],[0]]
     *  
     * 提示：
     * 1 <= nums.length <= 10
     * -10 <= nums[i] <= 10
     */

    private int[] arr;
    private List<List<Integer>> result;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        this.arr=nums;
        this.result=new ArrayList<>();
        if(nums==null||nums.length==0){
            return result;
        }
        Arrays.sort(nums);
        dfs(0,new ArrayDeque<>());
        return result;
    }

    private void dfs(int index, Deque<Integer> path) {
        if(index==arr.length){
            result.add(new ArrayList<>(path));
            return;
        }
        result.add(new ArrayList<>(path));
        for (int i = index; i < arr.length; i++) {
            if(i>index&&arr[i]==arr[i-1]){
                continue;
            }
            path.addLast(arr[i]);
            dfs(i+1,path);
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        No90子集II n=new No90子集II();
        int[] arr={4,4,4,1,4};
        List<List<Integer>> result = n.subsetsWithDup(arr);
        System.out.println(JSON.toJSONString(result));
    }

}
